﻿class Solution
{
public:
	int lengthOfLIS(vector<int>&nums)
	{
		int n = nums.size();
		vector<int> ret;
		ret.push_back(nums[0]);
		for (int i = 1; i < n; i++)
		{
			if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放 
			{
				ret.push_back(nums[i]);
			}
			else
			{
				// ⼆分插⼊位置 
				int left = 0, right = ret.size() - 1;
				while (left < right)
				{
					int mid = (left + right) >> 1;
					if (ret[mid] < nums[i]) left = mid + 1;
					else right = mid;
				}
				ret[left] = nums[i]; // 放在 left 位置上 
			}
		}
		return ret.size();
	}
};